package com.code.nowcoder;

import java.util.ArrayList;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/7/29 12:10
 */
public class The72_X {

    ArrayList<Integer>[] node;
    int[] vals;
    int m, ans;
    /**
     * 连通块
     * @param n 房间数量
     * @param k k块区域
     * @param m 代表每块区域的金币数要大于等于m
     * @param u u,v代表通道
     * @param v u,v代表通道
     * @param x x代表每个房间的金币数
     * @return bool布尔型
     */
    public boolean solve (int n, int k, int m, int[] u, int[] v, int[] x) {
        // write code here
        node = new ArrayList[n + 1];
        vals = new int[n + 1];
        this.m = m;
        for (int i = 1; i <= n; i++) {
            vals[i] = x[i - 1];
            node[i] = new ArrayList<Integer>();
        }
        /**
         * 如测试用例中的[1,1],[2,3]
         * 构建出来的 node 是
         * {
         *     {},
         *     {2, 3},
         *     {1},
         *     {1}
         * }
         */
        for (int i = 0; i < n - 1; i++) {
            node[u[i]].add(v[i]);
            node[v[i]].add(u[i]);
        }
        dfs(1, -1);
        return ans >= k;
    }

    /**
     *
     * @param u 要遍历的层数
     * @param fa 上次遍历的层数，防止发生循环遍历
     * @return 如果得到的数不大于 m 的话，那么返回这个值，大于的话返回 0，并把总数加1
     *  因为是一棵树，所以不管怎么样都只会跟它上面的那个点发生关联，有且仅有那一个交点
     */
    public int dfs(int u, int fa) {
        int val = vals[u];
        for (int i = 0; i < node[u].size(); i++) {
            if (node[u].get(i) != fa)
                val += dfs(node[u].get(i), u);
        }
        if (val >= m) {
            val = 0;
            ans++;
        }
        return val;
    }

    public static void main(String[] args) {
        The72_X the72 = new The72_X();
        the72.solve(2,2,1479, new int[]{1},new int[]{2},new int[]{1001,3357} );
    }
}
